#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 150010;

int n, m, q, len;
ll a[maxn], b[maxn], sum[maxn], ssum[maxn];

ll calc() {
  ll res = 0;
  vector<int> pos;
  per (i, len, 1) if (b[i] < 0) pos.emplace_back(i);
  rep (i, 1, len) if (b[i] > 0) {
    res += b[i];
    while (!pos.empty() && pos.back() <= i + m) {
      int nxt = pos.back();
      pos.pop_back();
      ll mn = min(b[i], -b[nxt]);
      b[i] -= mn, b[nxt] += mn;
      if (b[nxt] < 0) pos.emplace_back(nxt);
      if (!b[i]) break;
    }
    b[min(len + 1, i + m)] += b[i], b[i] = 0;
  }
  return res;
}

int main() {
  freopen("clear.in", "r", stdin);
  freopen("clear.out", "w", stdout);
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> n >> m >> q;
  rep (i, 1, n) cin >> a[i];
  rep (i, 1, n) {
    ll cval = a[i] - a[i - 1];
    if (i <= m) sum[i] = cval, ssum[i] = cval * ((n - i) / m);
    else sum[i] = sum[i - m] + cval, ssum[i] = ssum[i - m] + cval * ((n - i) / m);
  }
  int ok = 1;
  rep (i, 1, n - 1) ok &= (a[i] <= a[i + 1]);
  if (ok) {
    while (q--) {
      int l, r;
      cin >> l >> r;
      if (l == r) { cout << a[l] << '\n'; continue; }
      ll res = a[l] * ((r - l + m) / m);
      if (m <= 100) {
        rep (i, 0, m - 1) {
          int L = (l + 1) / m * m + i, R = r / m * m + i;
          while (L >= l) L -= m;
          while (L <= l) L += m;
          while (R < r) R += m;
          while (R > r) R -= m;
          ll s = sum[R] - (L - m >= 0 ? sum[L - m] : 0);
          ll ss = ssum[R] - (L - m >= 0 ? ssum[L - m] : 0);
          ll tmp = ss + s * ((r - R + m) / m - (n - R) / m);
          res += tmp;
        }
      } else {
        for (int p = r; p > l; p -= m) {
          int pl = max(l + 1, p - m + 1), pr = p;
          res += (a[pr] - a[pl - 1]) * ((r - p + m) / m);
        }
      }
      cout << res << '\n';
    }
    return 0;
  }
  while (q--) {
    int l, r;
    cin >> l >> r, len = r - l + 1, b[1] = a[l];
    rep (i, 2, len) b[i] = a[l + i - 1] - a[l + i - 2];
    b[len + 1] = -a[r];
    cout << calc() << '\n';
  }
}